package bfs;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

//本题只要模拟一般答案的过程，就可以看出和01矩阵一样的思路和代码
public class 地图中的最高点 {
	public static int[] dx={1,-1,0,0};
    public static int[] dy={0,0,1,-1};
    public int[][] highestPeak(int[][] isWater) {
        int m=isWater.length,n=isWater[0].length;
        int[][] dict=new int[m][n];
        for(int i=0;i<m;i++){
            Arrays.fill(dict[i],-1);
        }
        
        Queue<int[]> q=new LinkedList<>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(isWater[i][j]==1){
                    dict[i][j]=0;
                    q.offer(new int[]{i,j});
                }
            }
        }
        while(!q.isEmpty()){
            int sz=q.size();
            for(int i=0;i<sz;i++){
                int[] tmp=q.poll();
                int nx=tmp[0],ny=tmp[1];
                for(int k=0;k<4;k++){
                    int x=nx+dx[k],y=ny+dy[k];
                    if(x>=0&&y>=0&&x<m&&y<n&&dict[x][y]==-1){
                        dict[x][y]=dict[nx][ny]+1;
                        q.offer(new int[]{x,y});
                    }
                }
            }
        }
        return dict;
    }
}
